Several classes of cryptography algorithms are currently used to encrypt and decrypt data. Two classes of algorithms generally include symmetric key and asymmetric key (public key) algorithms. In asymmetric, or public key, cryptography, the key used to encrypt a message is not the same as the key used to decrypt it. The encryption key is public and widely distributed, and the decryption key is private and known only to the authorized recipient of the message. Public key algorithms, however, are very computationally intensive and the encryption and decryption operations are slow even on small amounts of data. Symmetric key algorithms, on the other hand, can be executed much faster while providing commensurate and even stronger levels of cryptographic security.
There are currently three prevailing published symmetric key algorithms: the Data Encryption Standard (DES), triple DES, and the Advanced Encryption Standard (AES). Each of these symmetric key algorithms divides plaintext and ciphertext into blocks of a specified size for encryption and decryption. This is known as a block cipher and generally involves operations on blocks of digits with a fixed, unvarying transformation. These algorithms are related in that each utilizes the same type of sub-operations to encrypt a block of plaintext into a block of ciphertext, and the same type of inverse sub-operations to decrypt a block of ciphertext into a block of plaintext. Block cipher algorithms have inherent limitations, however, which include slower execution speeds than stream ciphers (discussed below) and require more hardware complexity. Further, messages that do not match the block size (e.g. 128 bits) require the generation of padding text to complete the block. Additionally, block cipher algorithms encrypt identical blocks of plaintext into identical blocks of ciphertext using the same key.
Stream ciphers, on the other hand, encrypt the bits or bytes of a message one at a time, rather than in blocks as in block ciphers, and ideally do not encrypt identical plaintext into identical ciphertext. Further, stream ciphers typically execute at a higher speed than block ciphers and require lower hardware complexity, and can therefore be used in smaller applications, such as on mobile phones.
Certain aspects of the present invention relate to the stream cipher concepts designed and developed for use in rotor machines, electro-mechanical polyalphabetic devices that produced periodic sequences of monoalphabetic ciphers, each of which were used to encrypt a character of plaintext. Rotor machines were the standard cryptographic instruments adopted for military use by the Allied and German forces in the years before and during World War II. However, history records that most adversaries were generally successful at breaking enemy ciphers generated by such machines, mainly due to the methods adopted for regular stepping of one or more codewheels to new rotational positions before each character was encrypted, as well as flaws in the procedures for field operation and operator errors.
Rotor machines of this type were originally invented and patented by Edward H. Hebern. Improved versions were subsequently patented and made famous by Arthur Scherbius (e.g., ENIGMA) and later by Boris C. W. Hagelin (e.g., the eM209 and M211 machines), William Frederick Friedman (e.g., the Converter M-134-C, M-228, and M-325 machines), Laurence Safford and Seiler (the ECM Mark 11 machine, a.k.a. SIGBA) and others, including the TSEC/KL-7 (code named ADONIS) used by the National Security Agency into the 1970s.
The fundamental principle supporting each of these rotor machines is the serial application of a set of rotatable codewheels, each encrypting an input character via a monoalphabetic cipher to an output character that is then used as an input to the next codewheel in the sequence. Each intermediate encryption result in the sequence is affected by the rotational position of the corresponding codewheel. The initial input value is the plaintext byte and the final output value is the ciphertext byte. The state of the machine is then modified by the automatic rotation of one or more of the codewheels to a new position and the next character is then encrypted. Some rotor machines had additional features, such as a plugboard that supported a number of cables with jacks that switched pairs of various input plaintext values in an effort to thwart cryptanalysis attacks.
A codewheel was typically a circular wheel made of bakelite or ceramic material with wiring that mapped each input contact to a different output contact, establishing a single monoalphabetic cipher. Each codewheel could be rotated in these machines to as many positions as there were members in the plaintext alphabet, each different position producing a different ciphertext output character for the same plaintext input character. Consequently, for an alphabet size of 26 (α=26), each codewheel logically represented 26 different monoalphabetic ciphers as determined by its position. Even assuming an alphabet size of only 26, rotor machines supporting four codewheels (φ=4) generated approximately 450,000 (i.e., 264) different monoalphabetic ciphers before repeating an encryption with the same position of all codewheels. Later rotor machines, supporting six such codewheels (φ=6), had a cycle of approximately 309,000,000 (i.e., 266) monoalphabetic ciphers. Increasing either the size of the alphabet (α) or the number of codewheels (φ) expands the periodic cycle dramatically. For instance, the Soviet Union used a rotor machine with 10 codewheels each having a monoalphabetic cipher of 30 Cyrillic characters (α=30; φ=10), yielding approximately 590 trillion different monoalphabetic ciphers (i.e., 3010).
Regardless of the number of codewheels employed, conventional rotor machines were still subject to cryptanalysis attack. Successful cryptanalysis methods and strategies involved deriving statistical information about the structure and content of individual codewheels employed during the encryption sessions as well as the stepping algorithm that systematically drove the rotor machine to the next state. Since multiple codewheels were supplied which could be mounted in various combinations, order, and positions, the cryptanalysis efforts required to break the ciphertext produced by such machines was immense, particularly before the advent of modern computing and networked supercomputers. Even today, many historical messages enciphered by such rotor machines have yet to be deciphered simply because the available message traffic for particular sets of codewheels is too small for cryptanalysis to yield meaningful results.
In general, such prior art rotor machines were constructed with a “reflector” rotor that guided electronic impulses back through the set of rotors such that the ciphertext generated by each character of the alphabet was pair-wise symmetric. That is, in any given state, if encryption of the letter B produced the ciphertext letter X, then encryption of the letter X produced the ciphertext letter B. Thus, a rotor machine initialized in the same state could be used for either encryption of plaintext or decryption of ciphertext. While this strategy greatly simplifies operations by eliminating additional equipment and procedures, it introduces significant cryptanalysis vulnerabilities.
Furthermore, conventional rotor machines had major operational drawbacks in that they required costly and complex procedural efforts to provide operational support. Multiple sets of identical codewheels had to be constructed in secret and protectively distributed to authorized parties, and their introduction into operation had to be carefully coordinated. Many such sets were used for months, even years, due to the effort required to initiate new sets. Detailed operational instructions were necessary, directing painstakingly meticulous steps to ensure that the exact setup and initialization process for each base session was absolutely correct since any deviation resulted in unintelligible ciphertext even to authorized recipients. Usually these setup instructions changed daily, thus adding to the complexity. A typical operational procedure required the following steps to produce each daily base session:                A container with the correct set of codewheels was selected;        an exact subset of 4, 5 or 6 codewheels was extracted from the container;        the selected subset of codewheels was mounted into the machine in a specific order;        each mounted codewheel was adjusted to a specific position; and        cables were then connected to specific pairs of plugboard jacks.Once the daily base session settings were established, each encrypted message was usually preceded with directions specifying minor changes made to the base session settings prior to the encryption of the associated message. For example, one or more rotors might be adjusted to a different rotational position.        
Another significant issue was the manpower required for communications security. Thoroughly trained operators were absolutely essential for successful, secure communications using conventional rotor machines, and military forces had special attachments dedicated to such efforts. Multiple operators were assigned to oversee each session initiation and operation in an effort to avoid incorrect setups. Still, history reveals that during extended periods of operations, errors were unavoidable, many of them contributing to successful cryptanalysis efforts by adversaries. For example, some messages were transmitted that had been accidentally encrypted with the wrong settings, and then immediately retransmitted after being correctly encrypted using slightly different settings—a serious cryptographic mistake. Also, some procedures actually required duplicating portions of encrypted message headers, creating another serious vulnerability.
Early rotor machines utilized a regular odometer-like stepping algorithm for repositioning codewheels, which is a critical design flaw due to the fact that if each letter of the alphabet is processed while a number of codewheels are held fixed in their respective positions, the cryptographic effect produced by the fixed set is identical to that produced by a single monoalphabetic cipher. Thus, sequentially advancing the first codewheel until a full revolution occurs, then stepping the second codewheel, and resuming stepping of the first, is actually equivalent to having only two codewheels in use for a period determined by the size of the alphabet.
Later rotor machines addressed this vulnerability by introducing more complex and irregular stepping methods that made cryptanalysis much more difficult. One such example is the aforementioned TSEC/KL-7 that introduced two additional banks of secondary codewheels whose sole purpose was to produce a variable stepping sequence for the primary codewheels of the rotor machine. The TSEC/KL-7, however, was still subject to the other disadvantages of conventional, physical rotor machines, such as the complex procedures and operational support that were required for such devices. Even with the TSEC/KL-7, the cryptographic protection produced by such conventional rotor machines was basically generated by varying the initial installation, ordering, and positioning of a group of fixed codewheels selected from a relatively small, distributed set, and devising irregular methods of rotating the codewheels as encryption proceeded.
Many of these prior art rotor machines have now been implemented as software computer applications that exactly mimic their performance. However, such applications are merely simulations of prior art rotor machines. No instance of an improved virtual rotor machine has been publicly disclosed.